package cn.good.yan.sf.t6;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 6  二叉树
 *
 * @author shengren.yan
 * @create 2024-07-27
 */
public class BinaryTree {

    private int value;
    private BinaryTree left;
    private BinaryTree right;

    public BinaryTree() {

    }

    public BinaryTree(int value, BinaryTree left, BinaryTree right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    // 遍历二叉树
    public static List<List<Integer>> toList(BinaryTree old) {
        List<List<Integer>> all = new ArrayList<>();
        if (old == null) {
            return all;
        }
        LinkListQueue<BinaryTree> queue = new LinkListQueue<>();
        queue.offer(old);
        int num = 1;
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int i = 0;
            for (int j = 0; j < num; j++) {
                BinaryTree t = queue.pool();
                list.add(t.value);
                BinaryTree l = t.left;
                if (l != null) {
                    queue.offer(l);
                    i++;
                }
                BinaryTree r = t.right;
                if (r != null) {
                    queue.offer(r);
                    i++;
                }
            }
            num = i;
            all.add(list);
        }
        return all;
    }

    // Z型遍历二叉树
    public static List<List<Integer>> ZtoList(BinaryTree old) {
        List<List<Integer>> all = new ArrayList<>();
        if (old == null) {
            return all;
        }
        LinkListQueue<BinaryTree> queue = new LinkListQueue<>();
        queue.offer(old);
        int num = 1;
        boolean flag = true;
        while (!queue.isEmpty()) {
            LinkedList<Integer> list = new LinkedList<>();
            int i = 0;
            for (int j = 0; j < num; j++) {
                BinaryTree t = queue.pool();
                if (flag) {
                    list.offerLast(t.value);
                } else {
                    list.offerFirst(t.value);
                }
                BinaryTree l = t.left;
                if (l != null) {
                    queue.offer(l);
                    i++;
                }
                BinaryTree r = t.right;
                if (r != null) {
                    queue.offer(r);
                    i++;
                }
            }
            flag = !flag;
            num = i;
            all.add(list);
        }
        return all;
    }


    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree(
                1,
                new BinaryTree(
                        2,
                        new BinaryTree(4,
                                new BinaryTree(8, null, null),
                                new BinaryTree(9, null, null)),
                        new BinaryTree(5,
                                null,
                                null)
                ),
                new BinaryTree(
                        3,
                        new BinaryTree(6,
                                null, null),
                        new BinaryTree(7,
                                null,
                                new BinaryTree(10, null, null)
                        )
                )
        );

//        List<List<Integer>> list = toList(tree);
//        System.out.println(list);

        List<List<Integer>> Zlist = ZtoList(tree);
        System.out.println(Zlist);


    }


}
